package com.c2b.algorithm.leetcode.base;


/**
 * <a href="https://leetcode.cn/problems/rotate-list/">旋转链表(Rotate List)</a>
 * <p>给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：head = [1,2,3,4,5], k = 2
 *                      1   ->  2   ->  3   ->  4   ->  5
 *          rotate1     5   ->  1   ->  2   ->  3   ->  4
 *          rotate      4   ->  5   ->  1   ->  2   ->  3
 *      输出：[4,5,1,2,3]
 *
 * 示例 2：
 *      输入：head = [0,1,2], k = 4
 *                      0   ->  1   ->  2
 *          rotate1     2   ->  0   ->  1
 *          rotate2     1   ->  2   ->  0
 *          rotate3     0   ->  1   ->  2
 *          rotate4     2   ->  0   ->  1
 *      输出：[2,0,1]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *      <li>链表中节点的数目在范围 [0, 500] 内</li>
 *      <li>-100 <= Node.val <= 100</li>
 *      <li>0 <= k <= 2 * 10^9</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/4/27 10:30
 */
public class LC0061RotateList_M {

    static class Solution {
        public ListNode rotateRight(ListNode head, int k) {
            // 如果链表中无节点或只有一个节点、旋转次数为0时，直接返回
            if (head == null || head.next == null || k == 0) {
                return head;
            }
            // 计算链表中节点的个数
            ListNode currNode = head;
            int nodeNum = 0;
            while (currNode != null) {
                ++nodeNum;
                currNode = currNode.next;
            }
            // n个节点旋转n的倍数次相当于没旋转
            k = k % nodeNum;
            if (k == 0) {
                return head;
            }
            // 找到要旋转节点的前一个节点
            ListNode fast = head;
            ListNode slow = head;
            // 快慢指针，让快指针先走 步，然后快慢指针同时走，直到快指针走到链表尾部，此时慢指针的下一个节点就是新的链表头节点。
            for (int i = 0; i < k; i++) {
                fast = fast.next;
            }
            while (fast.next != null) {
                fast = fast.next;
                slow = slow.next;
            }
            ListNode secondListHead = slow.next;
            slow.next = null;
            fast.next = head;
            return secondListHead;
        }
    }


    /**
     * 考虑先将链表围成一个环
     */
    public ListNode rotateRight2(ListNode head, int k) {
        // 如果链表中没有节点或者只有一个节点，直接返回。k=0无需反转，直接返回
        if (k == 0 || head == null || head.next == null) {
            return head;
        }
        // 记录链表的长度
        ListNode currNode = head;
        int len = 1;
        while (currNode.next != null) {
            ++len;
            currNode = currNode.next;
        }
        // 如果k是链表长度的倍数，直接返回。反转后的结果与未反转的结果相同，相当于没反转。
        // 所以需要反转的次数可以更新为：k = k%len
        if ((k = k % len) == 0) {
            return head;
        }
        // 到达尾节点，让尾节点指向头节点。将链表形成环
        currNode.next = head;
        // 回到头节点
        currNode = currNode.next;
        // 走 len-k-1步
        for (int i = 0; i < len - k - 1; i++) {
            currNode = currNode.next;
        }
        ListNode res = currNode.next;
        currNode.next = null;
        return res;
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(3);
        head1.next.next.next = new ListNode(4);
        head1.next.next.next.next = new ListNode(5);
        ListNode head2 = new ListNode(0);
        head2.next = new ListNode(1);
        head2.next.next = new ListNode(2);
        Solution solution = new Solution();
        Printer.printListNode(solution.rotateRight(head1, 2));
        Printer.printListNode(solution.rotateRight(head2, 4));
    }
}
